DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT



     RESEARCH PROPOSAL SUBMITTED TO WALTER E. DISNEY ENTERPRISES



                                 BY



                     Computer Science Department

                  School of Humanities and Sciences

                         Stanford University



				IN



        COMPUTER-AIDED ANIMATION OF THREE-DIMENSIONAL OBJECTS





                    Co-Principal Investigators: 



                            JOHN McCARTHY

                    Professor of Computer Science



                            BRUCE BAUMGART

                Research Associate in Computer Science





                      This is a new request
             The desired starting date is January 1, 1974.
          The total amount requested for 24 months is $ 214,881
ABSTRACT:

	This is a request for  a grant of $ 214,881 to  support a two
year   reseach  program   in  computer   aided  animation   of  three
dimensional  objects.     Existing  computer   graphics  and   design
technology is reviewed  and new ideas are presented.   Specific ideas
developed concern  3-D representation,  3-D acquistion,  and language
extensions for geometric modeling.  The competence of  the authors is
advertised;  the facilities of  the Stanford  Artificial Intelligence
Project are outlined; and a budget and work plan are submitted.


CONTENTS:

	1. IDEAS AND WORK ALREADY DONE 

	2. WHAT WE PROPOSE TO DO 

	3. PREVIOUS WORK AT STANFORD 

	4. RELATION TO WORK DONE ELSEWHERE 

	5. FACILITIES AT STANFORD A.I. LAB 

	6. BIOGRAPHIES

	7. BIBLIOGRAPHY

	8. BUDGET

1. IDEAS AND WORK ALREADY DONE.

	The proposed work  is based on  the following ideas  and work
already done:

i. Explicit 3-D Object Representation.

	An   effective  way   of   obtaining   2-D  drawings   of   a
three-dimensional object  is to derive the  drawings from an explicit
computer  model  of  the   three-dimensional  object.  Sequences   of
perspective drawings  of the  object are obtained  automatically from
the  three-dimensional description,  with the  hidden surfaces of the
object  removed  and  appropriate  shading  and   coloring  provided.

ii. Object Generation from Physical Description.

	A convenient way of  making an explicit computer model  of an
object  is to simulate  the process of building the object.  That is,
the  description  of   how  to  build  an   object  is  an   implicit
representation of the  object.  For example it is  easier to describe
Figure 2  as a  dodecahedron with a regular five  pointed star shaped
hole cut through it,  than it is to draw the figure  with a light pen
or to list the loci of its vertices.

iii. Language Extension.

	Rather than developing  new languages for  geometric modeling
and  mechanical drawing,   we believe  it is  best to extend  the old
languages: FORTRAN,    ALGOL and  LISP.    The elements  of  language
extension  include new  data types  for  the language,   general  low
level  primitives  for  manipulating  the  new  data  types,   and  a
convenient set of higher level operations.  The division  of the work
into high  level operations defined in terms  of low level primitives
is an  important part  of the  design because  it isolates  the  data
structure manipulating code.

iv. Object Representation from Physical Measurement,

	Another way to  get an explicit  computer model of  an object
is to derive  it from measurements made on an actual physical object,
2-D drawing, or picture.  For example, the physical object might be a
clay model  of the  thing being  designed. We  believe that  only the
lack  of appropriate  software  is preventing  the use  of television
cameras as an inexpensive, accurate, and automatic  means of entering
graphical data into a computer. (Figure 3)

v. Prejudice against Pens for Interactive Graphics Control.

	It has been  our recent experience that a  distinction should
be  made between using a  light pen (or sonic pen, Rand tablet, etc.)
for graphics input and using it for graphics editing and  control. We
observe  that when  adequate  keyboard edit,    control and  language
conventions  are provided the use  of the light pen diminishes to the
point where it is  only demonstrated to visitors who  expect graphics
to involve light  pens. One reason for this is  that when an operator
can do something exactly in a few keystrokes he does not bother  with
picking up the pen,  acquiring the pen tracker, and drawing.  A second
reason  is that a pen  is necessarily based on 2-D screen coordinates
in which overlapping  portions of a  3-D drawing can not be  directly
distinguished with a  light pen. Pen based editing  systems require a
keyboard  or button box in  any event,  so we  argue that an operator
who can  control and alter  a drawing  with his  hands always in  the
locality of the keyboard will  be more efficient than an operator who
has to use both a keyboard and a  pen. However, the use of a pen  (or
Rand  Tablet)  for  graphics  input,    such  as  tracing  chromosome
photographs into  the computer, is justifiable  and expedient but not
directly relevant to  editing a 3-D design.  That is, pens
are functionally replaceable by either TV cameras or keyboards.

vi. Mechanical Simulation.

	Information, such  as the  degrees of  freedom of motion,  is
included  in the object description  and can be used  to get pictures
of objects  in different  positions.   This  is demonstrated  in  the
enclosed  flip book  animation of  a mechanical  arm turning  a block
over.

vii. Photometric Simulation.

	Photometric information  such as the  location and  nature of
light  sources and  the light scattering  properties of  the objects'
surfaces can be included in the  model and used to compute the actual
appearance of solid opaque objects. (Figure 4)
2. WHAT WE PROPOSE TO DO.

	We  propose to  represent  and simulate  solid  objects in  a
computer  for the sake  of animation and script design.
Our two year goal  will be to automate as  much as possible the  task
of  creating  and altering   three-dimensional  data structures  from
which color film can  be derived.  The overall  project to
date has  been called  "geometric modeling" a  term which  we use  to
refer to  our particular combination of computer  graphics,  physical
world modeling,   image processing  and geometry.   Accordingly,  the
details of the  work we propose doing  will be presented in  terms of
the elements comprising a Geometric Modeling System.      

	Like  a computer,    the four  main elements  of  a geometric
modeling  system are memory, process, input and output. Starting with
memory, there are  the problems of representation (how  to describe a
physical object),  accessing (how to find a particular description by
name,   by location,  or by  whether it  is currently  in view),  and
efficiency (how  to keep the  size of storage  space down and  how to
dynamically allocate fast and slow memory resources).
	
	The presently  implemented explicit object  representation is
based on  polyhedron models of solid rigid  objects.  A simple object
called a body  is defined by  a surface  shell composed of  vertices,
edges and  faces that satisfy  the   Euler equation, V  - E + F  = 2.
Such  polyhedron bodies  are combined to  form compound  objects.  At
present,  curved objects are represented by  approximating them using
a  polyhedron  composed of  a  sufficient  number  of flat  polygonal
faces.   We propose  to  further develop   the appearance  of  curved
objects by automating the  assignment of polygonal facets to  a given
curved  surface.   Other  current  representation  problems  that  we
propose working on  include constructing  efficient (and  compatible)
object labelling, handling  mechanical properties  of an  object, and
better representing compound and flexible objects.

	A final  representation issue  we would  study is  that of  a
format   for  communication  of   three-dimensional   models  between
modeling systems.   Although   we  believe  that it is  too early  to
propose a standard  format, it is desirable to  design and promulgate
a  format  as  simple,  but  as  inclusive  as  possible;  it is also
desirable to  develop  formatible  I/O routines so  that new  formats
can be sent or received.

	The  usual  input  devices  to  a geometric  modeling  system
include keyboards,  light-pens,   joy-sticks,  buttons,  cameras  and
film scanners, of  which the most  important to this proposal  is the
keyboard, because it is currently the best device for language input.
Indeed, we believe  that we can  demonstrate that  a system based  on
keyboards can do  geometric control and editing better  than a system
based on  both a light pen and a keyboard.  With respect to language,
we are proposing two projects: first, we would extend the programming
languages  FORTRAN,   ALGOL and LISP  and second,   we would continue
to develop  our interactive edit  and control language. The  elements
of a language extension  include new data types (the  "memory" of our
system),  a  micro  language  of  primitive  operations and  a  macro
language of more complex operations.

	The micro language  is composed of  a small set  of primitive
functions  that  invoke  the  only  subroutines  allowed to  directly
create and alter the data  structure.  All the geometric  processors,
editors,    input,    output   and  higher  language  operations  are
implemented  in  terms of  these fewer  than  fifty primitives.   The
reason for having a two-level  system is to isolate and  minimize the
amount of  code that is  necessarily dependent on  the implementation
details of the particular higher  level language. Furthermore, it  is
possible to construct  primitives that are complete and  general with
respect   to  fundamental  principles  in   polyhedron  topology  and
geometry. For example,   we now have a  set of Euler primitives  that
can generate  any Eulerian  polyhedron (and only  Eulerian polyhedra)
as  well as a set  of Euclidean primitives for  applying the group of
Euclidean transformations.    With  more good  luck,   we  intend  to
isolate sets of primitives for mechanics and for image formation.

	The  macro  level  of  language  extension  is  comprised  of
operations that make it convenient to simulate building a  mechanical
model of  an object. The  present macro  level includes an  operation
for  "sweeping"  edges  into  faces,    and  faces  into  solids;  an
operation for "glueing" surfaces  together; an operation for  passing
"cutting"  planes  thru  an  object;  and a  most  powerful  trio  of
operations   for  forming   the  volume  union,     intersection  and
difference of two  given polyhedra. Since  polyhedra can be taken  as
either bounding  a finite solid volume  or a finite  empty volume, we
have found it convenient to draw some objects indirectly by  building
their  holes and  intersecting  the  holes  with their  simple  outer
shape.   Further macro  operations we  propose to code  would include
more  "imaginary"  ones  for   bending,    constraining,     filling,
enveloping,   and expanding  upon a  skeleton; as  well as  some more
"realistic"  operations that  would model regular  machine shop tools
such as  a lathe,   punch  and milling  machine; as  well as  machine
building processes such as welding, fastening and assembly. 

	Our  second language  project  is oriented  towards  edit and
control.   The  main  differences  between  an  interactive  graphics
editor  and  a  graphics programming  language  are  that  an  editor
carries along its  working context so that most arguments and data do
not have to be  explicitly named (because they  happen to be "at  the
top  of  the  stack")  and  that  they  are  visibly  intensified  or
otherwise  indicated on  the display  screen.   The advantage  of the
interactive editor is  that the  user is relieved  of having to  coin
and  call names of  things.   However,  the  disadvantage is  that he
cannot develop subroutines  of the power  available in a  programming
language, which  provides notation  for procedures,  arguments,   and
variables.   We plan to keep the  programming language level distinct
from the  control and  edit  language level;  although it  should  be
clear  that  both language  levels  are  calling the  same  primitive
execution routines.
	Besides language inputs,  a  geometric modeling system should
have  a way of  reading data that  is already in  graphical form. For
such input,  we propose using  a television camera. For example,   we
already have developed video  intensity contouring to rapidly provide
the  edges of  an  image in  a form  available for  graphics editing.
Although video  input  per  se is  of  secondary importance  to  this
proposal,  we happen to  have such hardware and software available at
Stanford and can make good use  of it with little additional  effort.
Furthermore,   video  (or  visual)  computer input  has  considerable
promise as a major input device of future computers.

	The  third element  of a  geometric  modeling system  is  its
(software) processors.   There are  language processors,   mechanical
simulators,  locus solvers,  image  analysis and image synthesis,  as
well  as  that  process, quite central  to three-dimensional drawing,
which is hidden  line (and  surface) elimination.   We have a  hidden
line  eliminator which  combines several  of the  existing techniques
and which can generate both line  drawings and video images; also  we
have reason to believe  that further work on our design  will yield a
hidden   eliminator  that  can  handle   apparently  curved  objects,
generate shadows,  use the coherence between successive images,   and
still be  fast without special  purpose hardware.  Since  the purpose
of  the processors  just  mentioned should  be sufficiently clear, we
shall skip  detailing their algorithms  and implementation,  although
this will  comprise the bulk of  the work and  publication we propose
to do.

	The fourth and final  element of our  modeling system is  the
output,    which  includes  dynamic  CRT  display,    video  display,
hardcopy  printing,   and  magnetic  tape.  Although  mundane,    the
numerical object descriptions  on conventional (nondisplay)  computer
media like  magnetic tape  is important  in making  the output  of an
interactive   display   system   available   for   further  automatic
processing or communication.  On the other  hand, a high quality  CRT
that can display  characters and vectors is now  and shall remain the
primary tool requisite to  developing interactive graphics  software.
Consequently,   nearly  a  third of  the  budget included  with  this
proposal is allocated  to aquiring such a CRT to enhance our existing
display system. The most  promising alternative to  a CRT is a  video
display. However, present  day video display systems  would require a
very  large computer  and fast memory  to achieve  the resolution and
speed of a CRT display.
Management Plan

	The single  focus of  responsibility for  management of  this
research   proposal  is   the  senor  principal   investigator,  John
McCarthy,  professor  of   Computer  Science,  Stanford   University.
Ignoring the overall system organization  and fine details, the goals
of the proposed project are summarized in the following list:

Items partially in hand, but requiring first year work:

	1. Representation of solid rigid three-dimensional polyhedra.
	2. Language extension of geometric primitives.
	3. Language extension of object building operations.
	4. A hidden line (and surface) eliminator.
	5. A geometric editor.

Second year items:
	
	6. A Script action language compiler.
	7. Generation of high quality color video from geometric models.
	8. Representation for the "appearance" of curved objects.
	9. Representation for flexible objects.
	10. Video acquisition of physical objects and 2-D artist drawings.
	11. Mechanical simulation: gravity, inertia tensors, collisions.
	12. Photometric simulation - shadows, multiple light sources.

	Since substantial  work has  already been  done on items  one
through  five,  they  would  be  included  in the  most  conservative
estimate of  our  potential achievements  over  the next  two  years.
Intermediate  expectations include  making considerable  progress and
original contribution  with respect to items one through ten, as well
as beginning work on the two kinds of simulators, items 11 amd 12. An
optimistic  expectation would  be to  finish everything.